#include <cstdlib>
#include <cassert>
#include <cstring>
#include <string>
#include <iostream>
#include <ctime>
#include "AI.h"

using namespace std;

int Refutation[NUM_STAGES][100];

void quickSort(int moves[], gameState children[], int score[], int beg, int end)
{
    int t_score, t_m;
    gameState t_gs;
    
    if (end > beg + 1)
    {
        int piv = score[beg], l = beg + 1, r = end;
        while (l < r)
        {
            if (score[l] >= piv)
                l++;
            else
            {
                r--;
                swap(score[l], score[r], t_score);
                swap(children[l], children[r], t_gs);
                swap(moves[l], moves[r], t_m);
            }
        }
        l--;
        swap(score[l], score[beg], t_score);
        swap(children[l], children[beg], t_gs);
        swap(moves[l], moves[beg], t_m);
        quickSort(moves, children, score, beg, l);
        quickSort(moves, children, score, r, end);
    }
}


int NegaScoutEndGame(gameState node, BoardState player, int alpha, int beta, int stage,
                     BitBoard blocked, int lastmove)
{
    if (stage == 92)
    {
        if (player == WHITE) return evaluateTerminal(node);
        else                 return -evaluateTerminal(node);
    }
    
    int moves[100];
    BitBoard effects[100];
    int best_move = 0;
    int mCount = getMoves(node, blocked, player, moves, effects);
    
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    if (mCount == 0)
    {
        if (lastmove == -1)
        {
            if (player == WHITE) return evaluateTerminal(node);
            else                 return -evaluateTerminal(node);
        }
        else
        {
            return -NegaScoutEndGame(node, next_player, -beta, -alpha, stage, blocked, -1);
        }
    }
    
    // increment stage count
    stage++;
    // build list of children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(node, player, moves[i], effects[moves[i]]); 
    
    OrderMoves(moves, children, mCount, player, blocked, stage, lastmove, stage > END_GAME_TRIVIAL);
    
    // perform negascout search
    int b = beta;
    for (int i = 0; i < mCount; i++)
    {
        int score = -NegaScoutEndGame(children[i], next_player, -b, -alpha, stage, blocked, moves[i]);
        
        if (alpha < score && score < beta && i != 0)
            score = -NegaScoutEndGame(children[i], next_player, -beta, -alpha, stage, blocked, moves[i]);
        
        if (score > alpha) 
        {
            best_move = moves[i];
            alpha = score;
        }
        if (alpha >= beta) 
        {
            if (lastmove != -1)
                Refutation[stage][lastmove] = best_move;
            return alpha;
        }
        
        b = alpha + 1;  
    }
    
    if (lastmove != -1)
        Refutation[stage][lastmove] = best_move;
                
    return alpha;
}

/* solve the end game */
int SolveEndGame(gameState gs, BoardState player, BitBoard blocked, int stage, int lastmove)
{
    int moves[100];
    BitBoard effects[100];
    int mCount = getMoves(gs, blocked, player, moves, effects);
    
    int best_move = -1;
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    
    int b = beta;

    
    // build list of children
    stage++;
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]); 
    
    OrderMoves(moves, children, mCount, player, blocked, stage, lastmove, stage > END_GAME_TRIVIAL);
    
    for (int i = 0; i < mCount; i++)
    {   
        int score = -NegaScoutEndGame(children[i], next_player, -b, -alpha, stage, blocked, moves[i]);
        
        if (alpha < score && score < beta && i != 0)
            score = -NegaScoutEndGame(children[i], next_player, -beta, -alpha, stage, blocked, moves[i]);
        
        if (score > alpha)
        {
            alpha = score;
            best_move = moves[i];
        }
        if (alpha >= beta) break;
        
        b = alpha + 1;
    }
    return best_move;
}

/* order moves using the best n policy
   #in, out# moves      ... input list of moves and output a reordered list
   #in, out# child      ... child game after each move has been applied
   #in#      mCount     ... number of moves
   #in#      player     ... the current player
   #in#      stage      ... stage the game is at 
   #in#      trivial    ... the ordering is trivial (only uses refutation)    */
void OrderMoves(int moves[], gameState children[], int mCount, BoardState player,
                BitBoard blocked, int stage, int lastmove, bool trivial)
{
    int start = 0;
    int t_m;
    gameState t_gs;
    
    if (!trivial)
    {
        int score[100];
        for (int i = start; i < mCount; i++)
        {
            if (player == WHITE)
                score[i] = evaluateGame(children[i], blocked, player, stage);
            else
                score[i] = -evaluateGame(children[i], blocked, player, stage);
            
        }
        quickSort(moves, children, score, start, mCount);
    }
    else if (lastmove != -1)
    {
        int index = getMoveIndex(Refutation[stage][lastmove], moves, mCount);
        if (index != -1)
        {
            swap(children[0], children[index], t_gs);
            swap(moves[0], moves[index], t_m);
        }
    }   
}

/* Compute negamax score for the node
   #in#  node       ... current game state
   #in#  player     ... player to move
   #in#  depth      ... depth of the subtree
   #in#  alpha      ... lower bound for optimum score
   #in#  beta       ... upper bound for optimum score
   #in#  stage      ... which stage the game is at (= number of pieces - 5)
   #in#  lastmove   ... the opponent's last move (-1 for no move)
   return           ... minimax score of the current node                   */
int NegaScout(gameState node, BoardState player, int depth, int alpha, int beta, 
              int stage, BitBoard blocked, int lastmove)
{
    if (stage == 92)
    {
        if (player == WHITE)
            return evaluateTerminal(node);
        else
            return -evaluateTerminal(node);
    }
    if (depth <= 0)
    {
        int value = evaluateGame(node, blocked, player, stage);
        if (player == WHITE)
            return value; 
        else
            return -value; 
    }
    
    int moves[100];
    int best_move = 0;
    BitBoard effects[100];
    gameState children[100];
    
    int mCount = getMoves(node, blocked, player, moves, effects);
    int b = beta;    
    BoardState next_player = player == BLACK ? WHITE : BLACK;
    
    // if current player has no move
    if (mCount == 0)
    {
        // neither player has move, we reached terminal position
        if (lastmove == -1)
        {
            if (player == WHITE)
                return evaluateTerminal(node);
            else
                return -evaluateTerminal(node);
        }
        else
            return -NegaScout(node, next_player, depth, -beta, -alpha, stage, blocked, -1);
    }
    
    // build children
    stage++;
    for (int i = 0; i < mCount; i++)
    {
        children[i] = applyMove(node, player, moves[i], effects[moves[i]]);
    }
   
    OrderMoves(moves, children, mCount, player, blocked, stage, lastmove, depth < TRIVIAL_DEPTH);
    
    // otherwise
    depth--;
    for (int i = 0; i < mCount; i++)
    {
        int score = -NegaScout(children[i], next_player, depth, -b, -alpha, stage, blocked, moves[i]);
        
        if (alpha < score && score < beta && i != 0)
        {
            score = -NegaScout(children[i], next_player, depth, -beta, -alpha, stage, blocked, moves[i]);
        }
        
        if (score > alpha)
        {
            alpha = score;
            best_move = moves[i];
        }
        
        if (alpha >= beta)
        {
            if (lastmove != -1)
                Refutation[stage][lastmove] = best_move;
            return alpha;
        }
        
        b = alpha + 1;
    }
    if (lastmove != -1)
        Refutation[stage][lastmove] = best_move;
    return alpha;
}

/* choose the best move 
   #in#  board      ... current board state
   #in#  player     ... current player
   return           ... best move (x, y) in the format x*10 + y             */
int chooseMove(Board & board, BoardState player, int depth, int end_game, int lastmove)
{
    int moves[100], best_move, mCount, stage;
    BitBoard effects[100];
    
    BitBoard blocked;
    
    gameState gs = parseBoard(board, blocked);
    
    initialiseBoardSpecific(blocked);

    stage = BitCount(gs.white | gs.black) - 5;
    
    if (stage >= 91 - end_game)
    {
        return SolveEndGame(gs, player, blocked, stage, lastmove);
    }
    mCount = getMoves(gs, blocked, player, moves, effects);
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    
    // build children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
    {
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]);
    }
    
    stage++;
    OrderMoves(moves, children, mCount, player, blocked, stage, lastmove, depth < TRIVIAL_DEPTH);
    
    int b = beta;
    depth--;   
    for (int i = 0; i < mCount; i++)
    {   
        int score = -NegaScout(children[i], next_player, depth, -b, -alpha, stage, blocked, moves[i]);
        
        if (alpha < score && score < beta && i != 0)
        {
            score = -NegaScout(children[i], next_player, depth, -beta, -alpha, stage, blocked, moves[i]);
        }
        
        if (alpha < score)
        {
            best_move = moves[i];
            alpha = score;
        }
        if (alpha >= beta)
            break;
            
        b = alpha + 1;
    }

	return best_move;
}

void initialiseAI()
{
    initialiseMasks();
    initialiseEvaluator();
}
